package com.fwpsl.tree;

/**
 * @author: 风戏fw
 * @date: 2024/3/26
 * @description: 二叉查询树（Binary Search Tree, BST）：是一种增删改查都很快的模型。
 * 特点：每个节点最多2个子节点；左子树所有节点的值 < 根节点的值；右子树的所有节点的值 > 根节点的值。
 */
public class BinarySearchTree {

    static class Node extends Tree.Node {
        Node(Integer value) {
            super(value);
        }

        @Override
        public Integer getVal() {
            return (Integer) super.getVal();
        }

        @Override
        public Node getLeft() {
            return (Node) super.getLeft();
        }

        @Override
        public Node getRight() {
            return (Node) super.getRight();
        }
    }

    private Node root;

    public BinarySearchTree() {
        this.root = null;
    }

    /**
     * 插入节点
     *
     * @param value
     */
    public void insert(int value) {
        root = insertRecursive(root, value);
    }

    private Node insertRecursive(Node node, int value) {
        if (node == null) {
            return new Node(value);
        }

        if (value < node.getVal()) {
            node.left = insertRecursive(node.getLeft(), value);
        } else if (value > node.getVal()) {
            node.right = insertRecursive(node.getRight(), value);
        } else {
            // 值相同，可选择不插入或更新节点值
            // 这里我们选择不插入
            return node;
        }

        return node;
    }

    // 查找节点
    public Node search(int value) {
        return searchRecursive(root, value);
    }

    private Node searchRecursive(Node node, int value) {
        if (node == null) {
            return null;
        }

        if (value < node.getVal()) {
            return searchRecursive(node.getLeft(), value);
        } else if (value > node.getVal()) {
            return searchRecursive(node.getRight(), value);
        } else {
            return node;
        }
    }

    // 删除节点
    public void delete(int value) {
        root = deleteRecursive(root, value);
    }

    private Node deleteRecursive(Node node, int value) {
        if (node == null) {
            return node;
        }

        if (value < node.getVal()) {
            node.left = deleteRecursive(node.getLeft(), value);
        } else if (value > node.getVal()) {
            node.right = deleteRecursive(node.getRight(), value);
        } else {
            // 节点有两个子节点
            if (node.left != null && node.right != null) {
                // 找到右子树中的最小节点
                Node temp = findMin(node.getRight());
                node.setVal(temp.getVal());
                node.right = deleteRecursive(node.getRight(), temp.getVal());
            }
            // 节点只有一个子节点或没有子节点
            else {
                Node temp = (node.getLeft() != null) ? node.getLeft() : node.getRight();
                if (temp == null) {
                    node = null;
                } else {
                    node = temp;
                }
            }
        }

        return node;
    }

    private Node findMin(Node node) {
        Node current = node;
        while (current.left != null) {
            current = current.getLeft();
        }
        return current;
    }

    // 主函数用于测试
    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();

        // 插入节点
        bst.insert(50);
        bst.insert(30);
        bst.insert(20);
        bst.insert(40);
        bst.insert(70);
        bst.insert(60);
        bst.insert(80);

        // 打印原始树的中序遍历结果
        System.out.println("Inorder traversal of the original tree:");
        TreeTraversal.inorderTraversal(bst.root);
        System.out.println();

        // 查找节点
        Node searchResult = bst.search(60);
        if (searchResult != null) {
            System.out.println("Found node with value: " + searchResult.getVal());
        } else {
            System.out.println("Node not found.");
        }

        // 删除节点
        bst.delete(40);

        // 打印删除节点后树的中序遍历结果
        System.out.println("Inorder traversal of the tree after deleting 40:");
        TreeTraversal.inorderTraversal(bst.root);
        System.out.println();
    }

}
